Secret calculation is a technique in which data processing is performed while concealing data by secret sharing. The secret sharing is a technique in which data is converted into a plurality of distributed values so that original data can be restored by using a certain number or more number of pieces of distributed values, while original data cannot be restored by using distributed values of which the number of pieces is smaller than the certain number. The secret sharing can be categorized into several kinds. Examples of the secret sharing include (k,n)-secret sharing, additive secret sharing, permutation data secret sharing, and the like.
The (k,n)-secret sharing is secret sharing in which a plain text which is inputted is divided into n pieces of shares so as to be distributed to n pieces of parties P=(p0, . . . , pn-1) in advance. The plain text can be restored when arbitrary k pieces of shares are provided. Any information on the plain text cannot be obtained from shares of which the number is smaller than k. Specific examples of types of the (k,n)-secret sharing include Shamir secret sharing, replicated secret sharing, and the like.
The additive secret sharing is (k,k)-secret sharing by the replicated secret sharing. The (k,k)-secret sharing represents a case where n=k is set in the (k,n)-secret sharing. In the (k,k)-secret sharing, it is impossible to restore a plain text until shares of all parties are collected. The additive secret sharing is the simplest secret sharing in which a plain text is restored only by adding up k pieces of shares.
The permutation data secret sharing is secret sharing performed while concealing permutation data. The permutation data is data representing the rearrangement way in rearrangement of data columns. When m pieces of data columns are rearranged, permutation data π having the volume m is data representing a bijective map π:Nm→Nm. Here, Nm represents a collection of non-negative integers which are smaller than an arbitrary integer m. For example, data of which elements in vectors x→∈(Nm)m are different from each other can be assumed as random permutation data having the volume m.
More specifically, a vector x→=(3,0,2,1) can be assumed as random permutation data having the volume 4. For example, it is assumed to rearrange the data column y→=(1,5,7,10) by the vector x→. 1 which is the 0th element of the data column y→ is moved to the third position represented by the 0th element of the vector x→. 5 which is the first element of the data column y→ is moved to the 0th position represented by the first element of the vector x→. In a similar manner, 7 is moved to the second position and 10 is moved to the first position. As a result, the post-permutation data column z→=(5,10,7,1) is obtained.
In the permutation data secret sharing, permutation data is concealed by the following procedure. It is assumed that there are N pieces of k party groups of columns P=ρ0, . . . , ρN-1. For example, when k=2, each k party group ρi is a set (p0,p1) of the party p0 and the party p1, a set (p0,p2) of the party p0 and the party p2, or the like. It is assumed that all parties in each k party group ρi mutually share the permutation data πρi and the permutation data πρi is not informed to a complement ρ i. Further, a corresponding plain text is assumed to be π0(π1( . . . (πN-1(I)) . . . )). Here, I represents permutation in which output is performed in the same arrangement as that of input, that is, identical permutation. In this case, if the k party groups of columns P=ρ0, . . . , ρN-1 is set so that “(condition 1) any complement ρ i satisfies ρ⊆ρ i with respect to an arbitrary k−1 party group ρ”, any permutation data πρi is unknown in any coupling of the k−1 party.
For example, when the number n of parties satisfies n≥2k−1, the above-mentioned condition 1 is satisfied if the column P of the k party groups is set as a collection including all the k party groups. Further, when the number n of parties satisfies n>2k−1, the above-mentioned condition 1 is sometimes satisfied even if not all the k party groups are included. For example, when k=2 and n=4, the condition 1 is satisfied though {(p0,p1),(p2,p3)} does not include all the k party groups.
The secret random permutation is a technique for performing permutation of an inputted data column in a random manner while concealing the permutated orders even from a processing executor. As a conventional technique for performing the secret random permutation, the technique described in Non-patent Literature 1 is disclosed.
As a basic form of the secret random permutation described in Non-patent Literature 1, permutation data secret sharing values <π> are generated with the input of the column [a→] of (k,n)-secret sharing values so as to output the column [b→]=([aπ(0)], . . . , [aπ(m-1)]) of (k,n)-secret sharing values. At this time, it is characterized that any parties do not know the plain text π of the permutation data secret sharing values <π>, that is, the permutated order in the data column. As specific processing, the party p∈ρi which belongs to the k party collection ρi performs normal permutation processing, which is not a secret calculation, with respect to each sub share πρi in permutation data secret sharing so as to generate ([aπρi(0)], . . . , [aπρi(m-1)]) from the input [a→]=([a0], . . . , [am-1]) and performs redoing of the secret sharing of ([aπρi(0)], . . . , [aπρi(m-1)]) by processing called resharing in a repeated manner.
The following three types of secret random permutation can be conceivable based on the difference in forms of an input and an output. The first type is a case where both of an input and an output are (k,n)-secret sharing values. The second type is a case where an input is a (k,n)-secret sharing value and an output is a disclosed value. The third type is a case where an input is a disclosed value and an output is a (k,n)-secret sharing value. In the case where an input is a disclosed value, the above-described processing of the basic form is performed after the disclosed value is subjected to secret sharing to be secret sharing values. Further, in the case where an output is a disclosed value, disclosed processing is performed after the above-described processing of the basic form is performed. A disclosed value is a value which is known by all parties. The disclosed processing represents that all parties transmit own shares to other all parties and secret sharing is restored from the shares which are received by all parties.